#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

bool solve(int row, int col, vector<vector<int>> &board);

bool isValidAtPosition(int value, int row, int col, vector<vector<int>> &board) {
    //检查行
    bool rowIsValid = find(board[row].begin(), board[row].end(), value) == board[row].end();

    //检查列
    bool colIsValid = true;
    for(vector<int> v : board){
        if(v[col] == value){
            colIsValid = false;
            break;
        }
    }

    if(!rowIsValid || !colIsValid){
        return false;
    }

    int rowStart = row / 3 * 3;
    int colStart = col / 3 * 3;

    bool isGridValid = true;
    for(int r = rowStart; r < rowStart + 3; ++r){
        for (int c = colStart; c < colStart + 3; ++c) {
            // value 已经在 row,col 所属的九宫格上了，所以不⾏。
            if (board[r][c] == value) {
                return false;
            }
        }
    }

    return true;
} 

bool tryDigitsAtPosition(int row, int col, vector<vector<int>> &board) {
    // 在 row,col 的位置，尝试从 1 到 9 插⼊
    for (int i = 1; i < 10; ++i) {
        if (isValidAtPosition(i, row, col, board)) {
            // 如果某⼀个值 i 可⾏，就把 i 设置到棋盘上
            board[row][col] = i;
            // 并尝试⽤刚才定义的 solve 函数继续求解下⼀列
            if(solve(row, col + 1, board)) {
                // 如果最终 solve 返回 true，表⽰数独已经解完了
                // 因此，我们返回 true。
                return true;
            }
        }
    }
    // 如果 1 - 9 尝试过之后都不可⾏，我们就把之前设置在 row,col 的值清 0，返回 false。
    // 这会导致 solve 函数调⽤回退到求解上⼀个位置的过程，继续尝试其它值。
    board[row][col] = 0;
    return false;
}

bool solve(int row, int col, vector<vector<int>> &board) {
    // 如果 col 已经到⾏尾
    if (col == board[row].size()) {
        ++row; // 就移动到下⼀⾏
        col = 0; // 并从下⼀⾏的起始元素开始
        if (row == board.size()) {
            // 此时，如果 row 已经超过了最后⼀⾏，说明整个数独都解完了
            // 我们就返回 true。
            return true;
        }
    }

    // 如果当前位置是 0，表⽰这是⼀个需要填值的位置
    if (board[row][col] == 0) {
        // TODO
        // 我们要尝试在 row,col 这个位置填⼊ 1 〜 9，看哪个可⾏
        // 并返回填⼊的结果。
        return tryDigitsAtPosition(row, col, board);
    }
    else {
        // 如果 row,col 这个位置已经有数字了，我们就跳过，继续处理 row,col+1 这个位置
        // 递归调⽤ solve 就好。
        return solve(row, col + 1, board);
    }
}

   
int main(int argc, char const *argv[])
{
    vector<vector<int>> sudoku {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    }; 

    bool res = solve(0, 0, sudoku);

    cout << res << endl;
    for(int i = 0; i < sudoku.size(); ++i){
        for(int j = 0; j < 9; ++j){
            cout << sudoku[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}
